Quản Mai Cốc

Quản Mai Cốc (tiếng Trung: 管梅谷 sinh năm 1934 tại Thượng Hải) là một nhà nghiên cứu người Trung Quốc, người "đã trở thành một trong những chuyên gia hàng đầu về quy hoạch toán học ở Trung Quốc". Ông được biết đến với nghiên cứu về bài toán người đưa thư Trung Hoa, và là hiệu trưởng trường Đại học Sư phạm Sơn Đông.

Những đóng góp nghiên cứu

Một ví dụ về bài toán kiểm tra tuyến đường của Quản (các cạnh và trọng số màu đen) và giải pháp tối ưu (gấp đôi các cạnh màu đỏ để tạo thành một đồ thị Euler)

Quản Mai Cốc được biết đến từ bài toán kiểm tra tuyến đường. Bài toán này là dạng tổng quát của bài toàn đường đi Euler, trong đó đề bài là một đồ thị cạnh-trọng số và mục tiêu là phải tìm ra một đường đi khép kín có tổng trọng số nhỏ nhất và có thể đi qua được tất cả các cạnh của đồ thị ít nhất một lần. Ứng dụng của nó bao gồm những vấn đề trong quy hoạch giao thông chẳng hạn như lập kế hoạch đường đi cho một đoàn xe ủi tuyết để cào những con đường trong một thành phố trong một khoảng thời lượng là tối thiểu.

Quản Mai Cốc đã làm giảng viên tại Đại học Sư phạm Sơn Đông trong suốt thì kỳ Đại nhảy vọt 1958–1960, lúc mà các nhà toán học Trung Quốc được khuyến khích nghiên cứu những bài toán mang tính thực tiễn. Ông đã xuất bản công trình nghiên cứu về bài toán kiểm tra tuyến đường của mình vào năm 1960, và bài báo của ông được dịch sang tiếng Anh vào năm 1962. Nó đã thu hút sự chú ý của Jack Edmonds, người đã đặt tên khác cho bài toán này là "Bài toán người đưa thư Trung Hoa", để vinh danh Quản Mai Cốc, và đã chứng minh được rằng bài toán này có thể được giải một cách tối ưu trong thời gian đa thức.

Một trong những đóng góp của Quản Mai Cốc sau đó là chứng minh bài toán windy postman problem là NP-đầy đủ; đây là dạng tổng quát của bài toán kiểm tra tuyến đường trong đó chi phí đi qua một cạnh phụ thuộc vào hướng mà nó đi.

Sự nghiệp

Quản Mai Cốc hoàn thành việc học vào năm 1957 tại Đại học Sư phạm Hoa Đông ở Thượng Hải, và cùng năm đó ông đã vào khoa của trường Đại học Sư phạm Sơn Đông. Ông từng làm hiệu trưởng đại học Sư phạm Sơn Đông từ năm 1984 đến 1990. Từ năm 1990 đến 1995, ông trở thành trưởng khoa vận trù học tại Đại học Phục Đán, sau đó ông chuyển sang trường kinh doanh thuộc Đại học RMIT ở Úc.

Một số ấn bản

• Kwan, Mei-ko (1960), “奇偶点图上作业法” [Graphic programming using odd or even points], Acta Mathematica Sinica (bằng tiếng Trung), 10: 263–266, MR 0162630, Bản gốc lưu trữ ngày 21 tháng 4 năm 2017, truy cập ngày 30 tháng 11 năm 2017. Translated in Chinese Mathematics 1, American Mathematical Society, 1962, pp. 273–277.
• Guan, Meigu; Zheng, Handing (1983), 线性规划 [Quy hoạch tuyến tính] (bằng tiếng Trung), Shandong Science and Technology Press.
• Guan, Meigu (1984), “On the windy postman problem”, Discrete Applied Mathematics, 9 (1): 41–46, doi:10.1016/0166-218X(84)90089-1, MR 0754427.
• Guan, Meigu (1989), “Graph theory in China”, Graph theory and its applications: East and West (Jinan, 1986), Annals of the New York Academy of Sciences, 576, New York: New York Academy of Sciences, tr. 203–218, doi:10.1111/j.1749-6632.1989.tb16400.x, MR 1110817.